Cryptographic data security techniques secure data by encrypting the data with a key. The decrypted data can only be recovered using the key. The key is selected to be sufficiently long that a malicious intruder cannot guess the key by exhaustive trial and error, even with the use of substantially large amounts of computing resources. Therefore, the security of the data has been transferred to the security of the key. Often, it is desirable to store the key so that access to the key is controlled by a pass-phrase or PIN (Personal Identification Number) that is short enough for a human user to remember easily. This would conveniently enable the human user to use his PIN to recover the key, and then use the key to recover the encrypted data. Unfortunately, if the PIN is short enough for the human to remember, it is also short enough for a malicious intruder to guess by exhaustive trial and error, thereby undermining the security of the key, and hence the security of the encrypted data. This has long been a vexing problem in data security. In the present invention, we will offer a solution to this problem, using a fundamentally new technique called cryptographic camouflaging. In contrast with conventional methods that aim to conceal the key, this new technique will camouflage the key by embedding it in a multitude of apparently similar keys. The keys are sufficiently different that the legitimate owner of the data can locate the correct key without any difficulty, using a short PIN that he can remember. Yet, the keys are sufficiently alike that a malicious intruder will find all of them equally plausible. The only way the intruder can select the correct key via trial and error, is to verify his trials with either the owner of the key, or with an administrative authority, thereby exposing himself. While the discussion that we will present is in the exemplary context of storing private keys for digital signatures, those skilled in the art will readily recognize that the technique of cryptographic camouflage can be used to secure other forms of data.
We now return to our discussion of the background of the invention. In asymmetric cryptographic methods such as RSA, each user holds a matched pair of keys, a private key and a public key. The private key and the public key form a unique and matched pair in that messages (e.g., messages, data, code, and any other digitally representable information including other cryptographic keys or cryptographic representations of information) that are encrypted with the private key can only be decrypted with the public key and vice versa. This one-to-one correspondence between the private key and the public key can be used to create digital signatures for electronic messages and transactions. In order to sign an electronic message, a use can simply encrypt the message with his private key. He would then attach his public key to the encrypted message and send it to the recipient. Alternatively, the user would not attach his public key to the message, but the recipient could look up the user's public key in a directory of public keys. In either case, to verify the signature, the recipient would decrypt the message using the attached public key, and if the decryption is successful, the recipient is confident of the origin of the message.
As described above, the sender would have to encrypt the entire message with his private key to sign it, which is computationally expensive. To address this, it suffices to compute a short hash of fixed length, say 128 bits long, of the message and then encrypt the hash value. If the hash function is a good one, such as MD5, the chances of two distinct messages having the same hash value is extremely small. Therefore, digital signature methods typically compute hashes of messages, and encrypt only the hash value. The encrypted hash value and the public key of the sender are attached to the original message prior to transmission to the recipient. To verify the signature, the recipient would first compute the hash of the received message. If the computed hash value is the same as the decrypted form of the encrypted hash, the recipient is confident of the origin of the message.
In the foregoing, the strength of the signature verification process depends on the recipient's confidence that the public key attached to the message is indeed the public key of the purported owner. Anybody can generate a matched pair of keys can masquerade as the user, unless there exists a means to prevent such a masquerade. To this end, public keys are often certified by third-party notaries called certifying authorities or CAs for short. Examples of certifying authorities are commercial entities such as Verisign and Entrust. The CA binds a certifiee's public key with the certifiee's identity, and then signs the combined message with the CA's private key, to form the certifiee's public key certificate. Thus, a certificate holder would attach his public key certificate to the encrypted message prior to sending the message to the recipient. To check the sender's identity and the authenticity of his public key, the recipient verifies the CA's signature on the sender's public key certificate, using the CA's public key. Since there would only be a small number of widely trusted CAs, the CA's public key would be reliably and easily available to the recipient. Thus, public key signatures can be used for stranger-to-stranger authentication in that even if the recipient and the sender have no prior relationship, the recipient can verify the sender's signature as long as the recipient and the sender both trust a common CA.
The uniqueness and unforgeability of a user's signature depend very strongly on the ability of the user to keep his private key private. Anybody who has access to the private key of a user can masquerade as that user with complete anonymity. Hence, widespread use of digital signatures for electronic commerce and other applications will require technology for the secure storage of private keys. At present, it is widely believed that private keys are best stored by physically isolating them on hardware devices such as smart cards, Fortezza cards, PCMCIA cards and other compact hardware devices. Smart cards are credit-card sized cards that contain a microprocessor and some memory. The user's private key and public key certificate are written onto the memory. To use the card, the user would simply insert the card into an appropriate card reader connected to a host computer, and then enter his PIN to activate the card. If the correct PIN is entered, the on-card processor would release the private key for use on the host computer. If an incorrect PIN is entered, the processor would not release the user's private key. Some tamper-resistant smart cards are configured so that if incorrect PINs are entered on several consecutive activation attempts, the card locks up permanently. Some sophisticated smart cards (often called cryptocards) can perform cryptographic operations, so that the private key need never leave the smart card. The bytes to be processed enter the smart card from the host computer, are processed, and are then transmitted back to the host computer. Unfortunately, even cryptocards must rely on the host computer for transmitting the bytes back and forth from the card reader and are therefore not perfectly secure. A malicious host computer could simply substitute one message for another prior to transmission, so that the user thinks he is signing one message, while in fact he is signing another. Therefore, even cryptocards cannot combat malicious host computers.
While the smart card solves the problem of securely storing private keys, it suffers from several significant drawbacks:
    1) High Initial Cost: Smart cards require expensive additional hardware infrastructure in the form of smart card readers;    2) Administrative Overhead: Smart cards require administrative overhead for distribution and upkeep; and    3) Low User Convenience: The user cannot duplicate, backup or collate smart cards, owing to their tamper proof features.
A secure software-based key wallet that does not require additional hardware would mitigate some of the drawbacks of the smart card listed above. Unfortunately, there are no such solutions presently available. The standard technology that is used today for key storage, in products such as those of Microsoft and Netscape, offers very little protection against tampering, and can be broken into rather easily. Specifically, these key wallets store the private key in encrypted form, using the user's PIN as the encryption key. The PIN must be short enough for the user to remember, say a six-digit code. If such a software key wallet falls into the hands of a hacker, the hacker could exhaustively try all one million possible six-digit codes in an automated fashion on a personal computer within a few minutes, until he finds the code that opens the key wallet. At this point, the hacker knows that he has exactly the correct PIN, and has access to the user's private keys. Thus, the primary problem with providing a software-only key wallet are the competing requirements that the PIN be short enough for the user to remember, but long enough to make the key wallet tamper resistant.